package com.dily.study.demo.study;

/**
 * Date: 2022-03-10 星期四
 * Time: 15:27
 * Author: Dily_Su
 * Remark:
 * 二分查找法
 */
public class BinarySearch {

    /**
     * 二分查找
     *
     * @param nums   数组
     * @param target 目标数
     * @return index | -1
     */
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0)
            return -1;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] > target)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return -1;
    }

    /**
     * 求算数平方根
     *
     * @param x 原始数据
     * @return 算数平方根
     */
    public int mySqrt(int x) {
        if (x <= 2) return x;
        int left = 1;
        int right = x;
        while (left < right) {
            int mid = (left + right) / 2;
            if (x / mid == mid)
                return mid;
            else if (x / mid > mid)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return right;
    }
}
